package com.ryujung.linked_list.leetCode_19;

/*
 * @lc app=leetcode.cn id=19 lang=java
 *
 * [19] 删除链表的倒数第N个节点
 *
 * https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/description/
 *
 * algorithms
 * Medium (38.38%)
 * Likes:    799
 * Dislikes: 0
 * Total Accepted:    160.2K
 * Total Submissions: 417K
 * Testcase Example:  '[1,2,3,4,5]\n2'
 *
 * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 *
 * 示例：
 *
 * 给定一个链表: 1->2->3->4->5, 和 n = 2.
 *
 * 当删除了倒数第二个节点后，链表变为 1->2->3->5.
 *
 *
 * 说明：
 *
 * 给定的 n 保证是有效的。
 *
 * 进阶：
 *
 * 你能尝试使用一趟扫描实现吗？
 *
 */

// @lc code=start

/**
 * 思路:
 * 定义两个指针,一个先遍历到n+1
 * 第二个指针开始进行遍历,也就是两个指针相差n,
 * 当第一个指针遍历到空,第二个指针指向的就是倒数第n个节点
 * 例子:
 * 1->2->3->4     n=2
 * 首先让p1、p2都指向head节点
 * 第一步:p1 n+1次遍历到4
 * 第二部:p2 p1同时遍历(指向下一个),直到p1=null，此时p2指向倒数第n个节点的前一个，然后修改即可
 * <p>
 * 注意:考虑单节点、防止空指针异常
 * 解决方案：创建一个头节点node ，next指向head,
 * 这样在n+1次遍历时就不会因为是单节点导致空指针异常
 * <p>
 * 测试提交的时候，要把ListNode节点注释掉，否则提交报错
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode node = new ListNode(0);
        node.next = head;

        ListNode p1 = node, p2 = node;

        //第一个指针先前进到n+1
        for (int i = 0; i < n + 1; i++) {
            p1 = p1.next;
        }
        while (p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }

        p2.next = p2.next.next;//检查空指针异常
        return node.next;
    }

    // 以下为 2023年01月31日12:45:33追加
    /**
     * 思路1：
     * 单向链表，可以暴力遍历所有节点确定数量，然后再次遍历删除掉倒数第n个节点即可
     */
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        ListNode currentNode = head;
        int num = 0;
        while (currentNode != null) {
            num++;
            currentNode = currentNode.next;
        }

        // 第二次遍历
        currentNode = head;

        // 单独处理删除头部的情况
        if (num - n == 0) {
            return head.next;
        }

        for (int i = 1; i < num - n; i++) {
            currentNode = currentNode.next;
        }

        ListNode next = currentNode.next;
        if (next != null) {
            currentNode.next = next.next;
            next.next = null;
        }
        return head;
    }
    // 时间复杂度：O(n) 需要遍历链表
    // 空间复杂度：O(1) 固定数量的临时变量

    /**
     * 方法2：
     * 在遍历链表时，使用双指针，相差n个元素，
     * 这样以来，当先出法的指针到达末尾时，后出发的指针就是需要被删除的元素
     * 优点：
     * 一次链表遍历即可，避免对链表进行多次遍历
     * 注意：
     * 如果不想对删除head的情况进行单独处理，可以定义一个pre节点作为头部连接整个链表
     * 最后返回pre.next即可
     */
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode pre = new ListNode(0, head);

        ListNode first = pre;
        ListNode second = pre;
        for (int i = 0; i < n; i++) {
            // 题目给出 1 <= n <= sz ，不用考虑越界
            first = first.next;
        }

        while (first.next != null) {
            first = first.next;
            second = second.next;
        }
        // 先出发的指针到达链表的末尾，后出发指针的下一个元素就是需要被删除的元素
        ListNode needDeletedNode = second.next;
        second.next = needDeletedNode.next;
        needDeletedNode.next = null;

        return pre.next;
    }

}

//Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
// @lc code=end
